#include<iostream>
#include<cstdlib>
#include<string>
#include<ctime>
#include<fstream>

using namespace std;

struct Node {
	Node( int k = 0, int p = 0): key( k), priority( p), left( 0), right( 0), count( 0) {
	}

	Node* left;
	Node* right;
	int key;
	int priority;
	int count;
};

typedef Node* node_point;

struct DekartTree {
public:
    DekartTree(): tree_root( 0) {
		srand( time( NULL));
	}

	void Insert( int key) {
		Node* new_node = new Node( key, rand());
		InsertNode( tree_root, new_node);
	}

	int FindKTHKey( int k) {
		return KTHKey( tree_root, k);
	}

    void Erase( int key) {
        if( tree_root == 0) {
			return;
		}

        EraseNode( tree_root, key);
	}

	void PrintTree() {
		PrintNode( tree_root, 0, "");
	}

protected:
	node_point tree_root;

	DekartTree( node_point p) {
		tree_root = p;
	}

	int Count( node_point p) {
		return p == 0 ? 0 : p->count;
	}

	void CountUpd( node_point curr) {
		if( curr) {
			curr->count = 1 + Count( curr->left) + Count( curr->right);
		}
	}
	
	void Merge( node_point& root, node_point l, node_point r) {
		if( !l || !r) {
            root = l ? l : r;
		} else {
			if( l->priority > r->priority) {
				Merge( l->right, l->right, r), root = l;
			} else {
				Merge( r->left, l, r->left), root = r;
			}
		}
		CountUpd( root);
	}

	void Split( node_point root, int key, node_point& l, node_point& r) {
		if( !root) {
			l = r =0;
		} else {
			if( key < root->key) {
				Split( root->left, key, l, root->left), r = root;
			} else {
				Split( root->right, key, root->right, r), l = root;
			}
		}
		CountUpd( root);
	}

	int KTHKey( node_point root, int k) {
		if( Count( root->left) + 1 == k) {
			return root->key;
		} else {
			if( k < Count( root->left) + 1) {
				return KTHKey( root->left, k);
			} else {
				return KTHKey( root->right, k - Count( root->left) - 1);
			}
		}
	}

	void InsertNode( node_point& root, node_point it) {
		if( !root) {
			root = it;
		} else {
			if( it->priority > root->priority) {
				Split( root, it->key, it->left, it->right), root = it;
			} else {
				InsertNode( it->key < root->key ? root->left : root->right, it);
			}
		}
		CountUpd( root);
	}

	void EraseNode( node_point& root, int key) {
		if( root->key == key) {
			Merge( root, root->left, root->right);
		} else {
			EraseNode( key < root->key ? root->left : root->right, key);
		}
		CountUpd( root);
	}

	void PrintNode( node_point root, int depth, string s) {
		if( root) {
			
			for( int i = 0; i < depth; ++i) {
				cout<<"  ";
			}

			printf( "%s", s);
			cout<<' '<<root->key<<' '<<root->priority<<' '<<root->count<<endl;
			PrintNode( root->left, depth + 1, "l");
			PrintNode( root->right, depth + 1, "r");
		}
	}
};

int main() {
	freopen( "input.txt", "r", stdin);
	int n;
	cin>>n;
	DekartTree t;
	
	for( int i = 0; i < n ; ++i) {
		string s;
		
		cin>>s;
		

		if( s == "add") {
			int key;
			cin>>key;
			t.Insert( key);
		} else {
			if( s == "delete") {
				int key;
				cin>>key;
				t.Erase( key);
			} else {
				if( s == "print") {
					t.PrintTree(); 
				} else { 
					if( s == "KTHKey") {
						int key;
						cin>>key;
						int res = t.FindKTHKey( key);
						cout<<res<<endl;
					}
				}
			}
		}
	}
	return 0;
}